public class MaxDistance {
    private static class Node{
        public int value;
        public Node left;
        public Node right;
        public Node(int v) {
            this.value = v;
        }
    }

    private static class Info{
        public int maxDistance;
        public int height;//是一个更基本的信息，maxDistance需要依靠height才能求出
        public Info(int dis, int h){
            maxDistance = dis;
            height = h;
        }
    }

    public static Info process(Node head){
        if (head == null){
            return new Info(0, 0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + rightInfo.height + 1);
        return new Info(maxDistance, height);
    }

    private static int maxDistance(Node head){
        return process(head).maxDistance;
    }

    public static void main(String[] args) {
        Node head = new Node(1);

        head.left = new Node(2);

        head.right = new Node(3);

        head.left.left = new Node(4);

        head.left.right = new Node(5);

        head.right.left = new Node(6);

        head.right.right = new Node(7);

        head.right.right.right = new Node(8);
        System.out.println(maxDistance(head));
    }
}
